题目分析
我个人很喜欢这样的题目,题目难度适中,题意清晰,简洁。一道题上来就是一大段文字,比较晦涩的那种,我比较头痛。废话少说,小伙伴们看题。
排序
这个题目的意思是,有一个排好序的数组,其中有一个区间内数据打乱了,我们要找到这个最小的区间。
我的直观想法是,既然最后整个数组是有序的,那么我们可以将排好序的结果打印出来,然后进行对比,看一看从哪里开始不同的,到哪里相同不就是找到了这个区间吗?
算法的**时间复杂度为$O(nlog(n))$,空间复杂度为$O(n)$**。
1 | #include<iostream> |
数学
这个题目还有时间复杂度更短的做法,这用到了一些数学知识。如果第k个数,小于前k - 1个数的最大值,那么k一定是区间内的,因此我们可以找到最后一个k,当m > k时,都大于等于前m - 1个数的最大值。那么这个k就是这个区间的右端点。
同理,如果第k个数,大于后面所有数字的最小值,那么k也是这个区间内的,我们找到第一个k,当m < k时,都小于等于后面所有数字的最小值,那么这个k就是这个区间的左端点。
算法的**时间复杂度为$O(n)$,空间复杂度为$O(1)$**。
1 | #include<iostream> |
刷题总结
现在是寒假时间,寒假结束后,暑期实习,春招就要来到了,很多公司的提前批也是方法春天进行的,因此小伙伴们在放假长膘的期间内别忘了加强自己的coding能力。